﻿#define _CRT_SECURE_NO_WARNINGS 1


#include<stdio.h>
/*
===================================================================

给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

===================================================================
*/



int* majorityElement(int* nums, int numsSize, int* returnSize)
{
	if (nums == NULL || numsSize <= 1)    //数组为空或最多只有一个元素
	{
		*returnSize = numsSize;
		return nums;
	}
	//抵消阶段
	int major1 = nums[0];   //候选人1
	int major2 = nums[1];   //候选人2
	int count1 = 0;         //票数
	int count2 = 0;         //票数
	for (int i = 0; i < numsSize; i++)
	{
		if (nums[i] == major1)
		{
			count1++;
		}
		else if (nums[i] == major2)
		{
			count2++;
		}
		else if (count1 == 0)
		{
			major1 = nums[i];
			count1 = 1;
		}
		else if (count2 == 0)
		{
			major2 = nums[i];
			count2 = 1;
		}
		else
		{
			count1--;
			count2--;
		}
	}

	//检验阶段
	int n1 = 0, n2 = 0;
	*returnSize = 0;
	int* ret = (int*)malloc(2 * sizeof(int));
	for (int i = 0; i < numsSize; i++)
	{
		if (nums[i] == major1)
		{
			n1++;
		}
		else if (nums[i] == major2)
		{
			n2++;
		}
	}
	if (n1 > numsSize / 3)      //major1符合要求
	{
		ret[*returnSize] = major1;
		(*returnSize)++;        
	}
	if (n2 > numsSize / 3)     //major2符合要求
	{
		ret[*returnSize] = major2;
		(*returnSize)++;
	}
	return ret;
}